K1 = ""
K2 = ""
P10 = [3, 5, 2, 7, 4, 10, 1, 9, 8, 6]
P8 = [6, 3, 7, 4, 8, 5, 10, 9]
P4 = [2, 4, 3, 1]
IP_1 = [4, 1, 3, 5, 7, 2, 8, 6]
IP = [2, 6, 3, 1, 4, 8, 5, 7]
EP = [4, 1, 2, 3, 2, 3, 4, 1]
S1_box = [["01", "00", "11", "10"], ["11", "10", "01", "00"],
          ["00", "10", "01", "11"], ["11", "01", "00", "10"]]
S2_box = [["00", "01", "10", "11"], ["10", "00", "01", "11"],
          ["11", "10", "01", "00"], ["10", "01", "00", "11"]]

# 输入主密匙，获取K1,K2
def get_key(main_key):
    global K1
    global K2
    # print("请输入主密匙(10bit):")
    # main_key = input()
    main_key = substitue(main_key, P10)  # P10
    Ls1_L = main_key[:5]
    Ls1_R = main_key[5:10]
    Ls1_L = move(Ls1_L, 1)  # LS_1
    Ls1_R = move(Ls1_R, 1)
    K1 = Ls1_L + Ls1_R
    K1 = substitue(K1, P8)  # K1
    Ls2_L = move(Ls1_L, 2)  # LS_2
    Ls2_R = move(Ls1_R, 2)
    K2 = Ls2_L + Ls2_R
    K2 = substitue(K2, P8)  # K2
    # print("K1 =", K1)
    # print("K2 =", K2)

# 加密
def encrypt(Plainttext):
    # print("请输入加密信息:")
    # Plainttext = input()  # 明文
    Plainttext = ascii_to_binary(Plainttext)
    # print("转化为二进制数后为：", Plainttext)
    Plainttext = substitue(Plainttext, IP)  # IP置换
    L0 = Plainttext[:4]
    R0 = Plainttext[4:8]
    f1 = F(R0, K1)
    R1 = xor(L0, f1)
    L1 = R0
    f2 = F(R1, K2)
    L2 = xor(L1, f2)
    R2 = R1
    ciphertext = L2 + R2
    ciphertext = substitue(ciphertext, IP_1)
    # print("密文为:", ciphertext)
    ch = binary_to_ascii(ciphertext)
    return ch

# 解密
def decrypt():
    # print("请输入解密信息(8bit):")
    # ciphertext = input()
    ciphertext = ascii_to_binary(ciphertext)
    # print("转化为二进制数后为：" + ciphertext)
    ciphertext = substitue(ciphertext, IP)  # IP置换
    L2 = ciphertext[0:4]
    R2 = ciphertext[4:8]
    R1 = R2
    f2 = F(R2, K2)
    L1 = xor(f2, L2)
    R0 = L1
    f1 = F(L1, K1)
    L0 = xor(f1, R1)
    Plainttext = L0 + R0
    Plainttext = substitue(Plainttext, IP_1)
    print("明文：" + Plainttext)
    binary_to_ascii(Plainttext)
    return Plainttext

# 置换
def substitue(str, P):
    new_str = ""
    for i in range(len(P)):
        new_str += str[P[i]-1]
    return new_str

# 移位
def move(string, n):
    ch = list(string)
    new_ch = [''] * len(ch)
    for i in range(len(ch)):
        a = (i - n) % len(ch)
        if a < 0:
            if n == 1:
                new_ch[len(ch) - 1] = ch[i]
            if n == 2:
                if i == 0:
                    new_ch[len(ch) - 2] = ch[i]
                else:
                    new_ch[len(ch) - 1] = ch[i]
        else:
            new_ch[a] = ch[i]
    return ''.join(new_ch)

# f函数
def F(str, key):
    str = substitue(str, EP)  # 扩位以及置换
    # print("扩位以及置换str=",str)
    str = xor(str, key)  # 异或
    # print("异或str=",str)
    S1 = str[0:4]  # S1,S2
    S2 = str[4:8]
    S1 = searchSbox(S1, 1)  # S盒
    S2 = searchSbox(S2, 2)
    S = S1 + S2
    S = substitue(S, P4)  # P4置换
    return S

# s盒
def searchSbox(string, n):
    ret = string[0] + string[3]
    ret1 = string[1] + string[2]
    retu = ""
    if n == 1:
        retu = S1_box[int(ret, 2)][int(ret1, 2)]
    else:
        retu = S2_box[int(ret, 2)][int(ret1, 2)]
    return retu

# 异或
def xor(str, key):
    sb = []
    for i in range(len(str)):
        if str[i] == key[i]:
            sb.append("0")
        else:
            sb.append("1")
    return "".join(sb)

# ascii转二进制
def ascii_to_binary(string):
    num = bytearray(string, 'utf-8')
    s = num[0]
    binary = ""
    while s > 0:
        binary = str(s % 2) + binary
        s = s // 2
    if len(binary) < 8:
        for i in range(8 - len(binary)):
            binary = "0" + binary
    return binary

# 二进制转ascii
def binary_to_ascii(string):
    num = int(string, 2)
    ch = chr(num)
    # print("用ASCII编码表示为：", ch)
    return ch

# 寻找密钥
def findKey(ciphertext,Plainttext):
    for i in range(1024):
        binary = format(i, '010b')
        # print("binary=",binary)
        get_key(binary)
        # print("ciphertext=",ciphertext)
        # print("encrypt(Plainttext)=",encrypt(Plainttext))
        if ciphertext == encrypt(Plainttext):
            print("找到密钥为",binary)
            return binary
    print("没找到密钥")
    return None

if __name__ == "__main__":
    print("输入明文：")
    Plainttext = input()
    print("输入密文：")
    ciphertext = input()
    findKey(ciphertext,Plainttext)

# 第5关：封闭测试
# 根据实验，发现一对明密文对可能不止有一个密钥，例如明文q和密文B之间的密钥可以是1101001010和1100000000